The present invention relates to analysis of an image.
Lettera, C., Maier, M., Masera, L., and Paoli, C., "Character Recognition in Office Automation," in Cappellini, V. and Marconi, R., (eds.), Advances in Image Processing and Pattern Recognition, Elsevier Science Publishers, 1986, pp. 191-198, describe character recognition techniques based on feature extraction and statistical classification. As described on page 192, histograms of the black pixels are counted, for each character, along the horizontal, vertical, and diagonal directions, to obtain useful features. The vertical projection is illustrated in FIG. 1. Histogram vectors obtained with an interval width of one pixel are transformed into vectors of eight elements for further processing.
Tanaka et al., U.S. Pat. No. 4,847,912, describe a technique of detecting a space between words with an optical character reader. As shown and described in relation to FIGS. 2-6, the reader scans each printed line in the direction of its height from its beginning to its end sequentially at a predetermined interval. The intervals are identified either as containing a printed part, represented by a black bit, or as being all white, represented by a white bit. The number of continuous white bits between black bits is counted. The histogram of the counts has two peaks corresponding to gaps between letters and gaps between words. The histogram is used to determine a threshold value for detecting a space between words, so that the beginning of each word can be identified.
Toussaint, G. T., "Pattern Recognition and Geometrical Complexity," Proceedings of 5th International Conference on Pattern Recognition, Dec. 1-4, 1980, Vol. 2, IEEE, pp. 1324-1347, surveys geometrical structures used to solve various pattern recognition problems. Section 2 describes several basic computational structures that depend on distance between neighboring points in an image, including the Voronoi diagram and the Delaunay triangulation. Section 7 describes techniques for nearest neighbor searching; the straightforward approach of computing distance from a point to all other points can be improved upon by using the Voronoi diagram to create slabs and compartments within each slab; other techniques have been proposed for reducing the number of distance calculations. Section 11 describes visibility problems including visibility of a polygon from a point.
Borgefors, G., "Distance Transforms in Digital Images," Computer Vision Graphics and Image Processing, Vol. 34 (1986), pp. 344-371, describes distance transformations that convert a binary digital image, consisting of feature and non-feature pixels, into an image where each non-feature pixel has a value corresponding to the distance to the nearest feature pixel. To compute the distances with global operations would be prohibitively costly; the paper describes digital distance transformation algorithms that use small neighborhoods and that give a reasonable approximation of distance. Page 345 explains that such algorithms are based on approximating global distance in the image by propagating local distances, i.e. distances between neighboring pixels. The distance transformations are described in graphical form as masks, as shown in FIG. 2; the local distance in each mask-pixel is added to the value of the image pixel below it and the minimum of the sums becomes the new image pixel value. Parallel computation of such a distance transformation requires a number of iterations proportional to the largest distance in the image. Section 3, beginning on page 347, describes optimal distance transformations for different image sizes. Section 4, beginning on page 362, compares several examples, including computing the distance from an object or object contour, in Section 4.3, and computing a pseudo-Dirichlet or Voronoi tesselation, in Section 4.4.
Ahuja, N., and Schachter, B. J., Pattern Models, John Wiley and Sons, New York, 1983, Chapter 1, pp. 1-73, describe tessellations beginning at page 4. Section 1.3.5, beginning on page 15, describes Voronoi and Delaunay tessellations, indicating that a Voronoi polygon is the locus of points closer to a vertex than to any other vertex and that the Delaunay triangulation is a dual of a Voronoi tessellation. Algorithms for constructing the Delaunay triangulation are described beginning at page 22. Section 1.3.5.4, beginning on page 32, describes the use of the Voronoi polygon for neighborhood definition, reviewing other techniques for defining the neighborhood of a point and comparing them with the Voronoi approach. FIG. 1.3.5.4-2 shows how Voronoi neighbors of a point may be farther from it than nonneighbors, because Voronoi neighbors are not necessarily its nearest neighbors--the Voronoi neighbors of a point must surround it.
Mahoney, J. V., Image Chunking: Defining Spatial Building Blocks for Scene Analysis, Dep't. of Elec. Eng. and Comp. Sci., M.I.T., 1987 ("the Mahoney thesis"), pp. 31-37, describes techniques for detecting abrupt change boundaries by direct comparisons between neighboring elements. Pages 32-34 describe the directional nearest neighbor graph, useful for computing an explicit representation of the neighbors of each image property element, and compare it to the Voronoi dual.